public class MyStack {
    Deque<Integer> q1;
    Deque<Integer> q2;

    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }

    public void push(int x) {
        if(empty()) {
            q1.offer(x);
            return;
        }
        if(!q1.isEmpty()) {
            q1.offer(x);
            return;
        }else {
            q2.offer(x);
            return;
        }

    }

    public int pop() {
        if(!q1.isEmpty()) {
            int size = q1.size();
            int ret = q1.poll();
            for(int i = 0; i < size-1; i++) {
                q2.offer(ret);
                ret = q1.poll();
            }
            return ret;
        }else {
            int size = q2.size();
            int ret = q2.poll();
            for(int i = 0; i < size-1; i++) {
                q1.offer(ret);
                ret = q2.poll();
            }
            return ret;
        }
    }

    public int top() {
        if(!q1.isEmpty()) {
            int size = q1.size();
            int ret = q1.poll();
            for(int i = 0; i < size - 1; i++) {
                q2.offer(ret);
                ret = q1.poll();
            }
            q2.offer(ret);
            return ret;
        }else {
            int size = q2.size();
            int ret = q2.poll();
            for(int i = 0; i < size - 1; i++) {
                q1.offer(ret);
                ret = q2.poll();
            }
            q1.offer(ret);
            return ret;
        }
    }

    public boolean empty() {
        return q1.isEmpty() && q2.isEmpty();
    }
}